package com.ly.algorithm.leetcode.str;

import java.util.Stack;

/**
 * @Classname Probelm844
 * @Description
 * 给定 S 和 T 两个字符串，当它们分别被输入到空白的文本编辑器后，判断二者是否相等，并返回结果。 # 代表退格字符。
 *
 * 注意：如果对空文本输入退格字符，文本继续为空。
 *
 *  
 *
 * 示例 1.txt：
 *
 * 输入：S = "ab#c", T = "ad#c"
 * 输出：true
 * 解释：S 和 T 都会变成 “ac”。
 * 示例 2：
 *
 * 输入：S = "ab##", T = "c#d#"
 * 输出：true
 * 解释：S 和 T 都会变成 “”。
 * 示例 3：
 *
 * 输入：S = "a##c", T = "#a#c"
 * 输出：true
 * 解释：S 和 T 都会变成 “c”。
 * 示例 4：
 *
 * 输入：S = "a#c", T = "b"
 * 输出：false
 * 解释：S 会变成 “c”，但 T 仍然是 “b”。
 *
 * @Date 2020/10/19 9:26
 * @Author 冷心影翼
 */
public class Problem844 {

	public static void main(String[] args) {
		Solution844 solution844 = new Solution844();
		boolean b = solution844.backspaceCompare("a#c", "b");
		System.out.println(b);
	}
}


class Solution844 {
	public boolean backspaceCompare(String S, String T) {
		Stack<Character> s= new Stack<>();
		Stack<Character> t = new Stack<>();
		char[] charS = S.toCharArray();
		char[] charT = T.toCharArray();
		for(int i=0;i<charS.length;i++) {

			if(charS[i]!='#') {
				s.push(charS[i]);
				continue;
			}

			if(!s.isEmpty())
				s.pop();
		}
		for(int i=0;i<charT.length;i++) {


			if(charT[i]!='#') {
				t.push(charT[i]);
				continue;
			}
			if(!t.isEmpty())
				t.pop();
		}
		if(s.size()!=t.size()) {
			return false;
		}
		while (!s.empty()) {
			char c1 = s.pop();
			char c2 = t.pop();
			if(c1!=c2)
				return false;
		}
		return true;
	}
}